

#include <algorithm>
#include <iostream>
#include <queue>
#include <vector>
#include <stack>

#include "common/utils.hpp"

// 递归判断每个节点，分支可提前结束的情况先判断处理
bool isSameTree(TreeNode* p, TreeNode* q) {
    if (p == nullptr && q == nullptr) return true;
    if (p == nullptr || q == nullptr) return false;
    if (p->val == q->val) return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
    return false;
}

bool isSubtree(TreeNode* root, TreeNode* subRoot) {
    if (root == nullptr && subRoot == nullptr) return true;
    if (root == nullptr || subRoot == nullptr) return false;
    if (isSameTree(root, subRoot)) return true;
    else return isSubtree(root->left, subRoot) || isSubtree(root->right, subRoot);
}

extern TreeNode* commonRoot;

int main() {
    bool ret = isSubtree(commonRoot, commonRoot);
    std::cout << "is same: " << ret << "\n";
}